package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code94LongestCommonSubsequence {

    public int longestCommonSubsequence(String text1, String text2) {
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
//        return process(str1, str2, str1.length - 1, str2.length - 1);

        int m = str1.length;
        int n = str2.length;
        int[][] dp = new int[m][n];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        // i = 0;
        for (int c = 1; c < n; c++) {
            dp[0][c] = str1[0] == str2[c] ? 1 : dp[0][c - 1];
        }
        // j = 0
        for (int r = 1; r < m; r++) {
            dp[r][0] = str1[r] == str2[0] ? 1 : dp[r - 1][0];
        }
        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                dp[r][c] = str1[r] == str2[c] ? dp[r - 1][c - 1] + 1 : Math.max(dp[r - 1][c], dp[r][c - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }

    public int process(char[] str1, char[] str2, int i, int j) {
        if (i == 0 && j == 0) {
            // 都到了第一位
            return str1[0] == str2[0] ? 1 : 0;
        } else if (i == 0) {
            return str1[0] == str2[j] ? 1 : process(str1, str2, i, j - 1);
        } else if (j == 0) {
            return str1[i] == str2[0] ? 1 : process(str1, str2, i - 1, j);
        } else {
            if (str1[i] == str2[j]) {
                return process(str1, str2, i - 1, j - 1) + 1;
            } else {
                return Math.max(process(str1, str2, i - 1, j), process(str1, str2, i, j - 1));
            }
        }
    }
}
